﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace Simulated_Annealing
{

    class Program
    {
        public static Random rand;

        
        
        // Slower if true!!! Set to true if don't trust my efficient distance and capacity updates
        public static bool DEBUG = false;

        // Global variable, for convenience
        public static CVRPData vrpData;

        static void Main(string[] args)
        {
            
            Console.WriteLine("Welcome to our Simulated Annealing implementation");

            Stopwatch watch = new Stopwatch();

            watch.Start();

            Random random = new Random();

            rand = new Random();

            VRP network = new VRP();                            //initialize VRP problem
            List<Nodes> nodes = new List<Nodes>();
            network.lambda = 1.0F;                              //initialize lambda = 1 for parser

            // If there are command line arguments, the first one is the file name
            String inputfile;
            if (args.Length != 0)
                inputfile = args[0];
            else
                inputfile = "Example1.vrp";

            // Create the parser object, and read in all the data from file. This object can read ANY TSPLIB file. Code borrowed from HeuristicLab.
            TSPLIBParser myParser = new TSPLIBParser(inputfile);
            myParser.Parse();

            //sets network to parser values
            network.capacity = myParser.Capacity;
            network.costmatrix = network.ODmatrix(myParser); // calculate the OD matrix
            network.demandarray = myParser.Demands;
            network.numnodes = myParser.Dimension;
            network.optimal_solution = myParser.BestKnown;
            network.error = false;

            // Create the global vrp data object, using the parsed data
            Program.vrpData = new CVRPData(myParser);

            // Using ImryStefan's saving algorithm 
            CVRPSolution currentSolution = SavingsMethodHeuristic();
            double totalCostInitial = currentSolution.totalCost;
            int numRoutesInitial = currentSolution.listOfRoutes.Count();
            network.routes = network.convert(currentSolution);


            if (network.error == true)                          //if there is an error in the input file, report it
            {
                Console.WriteLine("There is an error in the input file!");
                return;
            }

            VRP originalnetwork = new VRP(network); //stores original network

            SimA.Nfeas = VRP.find_Nfeas(network, random);
            int numfeas = SimA.Nfeas;
            SimA.Initialize(network.numnodes, numfeas, network, random); //initialize all the variables in simulated annealing class
            List<double> initialtemps = new List<double>();
            initialtemps = VRP.find_temp(network, random);
            SimA.T_f = initialtemps[0];
            SimA.T_s = initialtemps[1];
            int R_check;

            R_check = SimA.R;
            
            VRP s_current = new VRP(network); //this will be used in the while loop to store the current VRP solution we examin
            VRP s_best = new VRP(network); //this will be used in the while loop to store the best VRP solution we've found so far
            s_current.route_clean(s_current);
            s_best.route_clean(s_best);

            while (watch.ElapsedMilliseconds < 120000)
            {
                //do the following each time you re-enter the while loop
                s_current.route_clean(s_current);
                int[,] routepairlist;
                routepairlist = Neighborhood.routepairlist(s_current, random); //generate a new route pair list that corresponds to s_current

                int counter = 0;  //counter: counts the number of times we rejected in a loop of the route pairs during one neighborhood search

                int routelengthcheck = routepairlist.GetLength(0);

                for (int i = 0; i < routepairlist.GetLength(0); i++) //goes through each in the route list of a particular neighborhood
                {

                    s_current.route_clean(s_current);
                    //calls the neighborhood function to create s_neighborhood as a change from s_current
                    VRP s_neighbor = new VRP(Neighborhood.Create_Neighborhood(s_current, i, routepairlist, nodes));
                    s_neighbor.route_clean(s_neighbor);

                    VRP s_neighbor2 = new VRP(Neighborhood.Create_Neighborhood2(s_current, i, routepairlist, nodes));
                    s_neighbor2.route_clean(s_neighbor2);

                    if (s_neighbor2.totalcost(s_neighbor2.routes, s_neighbor2) < s_neighbor.totalcost(s_neighbor.routes, s_neighbor))
                    {
                        s_neighbor = s_neighbor2;
                    }


                    //here we store the best neighborhood we have so far
                    if (s_current.totalcost(s_current.routes, s_current) < s_best.totalcost(s_best.routes, s_best))
                    {
                        //we want to make s_best the s_current
                        s_best = new VRP(s_current);
                        SimA.T_b = SimA.T_k;
                    }
                    // else we continue

                    double delta = s_neighbor.totalcost(s_neighbor.routes, s_neighbor) - s_current.totalcost(s_current.routes, s_current);//This will be the delta you want for your SA part, so copy this          

                    //BEGIN SIMULATED ANNEALING PROCESS

                    int acceptCheck = SimA.Run(delta, routepairlist.GetLength(0), counter);  //this will pass the delta to the simulated annealing class and do acceptance rejection
                    //SimA.Run will also update the temperature accordingly
                    //SimA.Run also accepts the size of the route list so that it can check for what kind of temperature update to do

                    R_check = SimA.R;  //just make sure the current R value is most up to date from the SimA class


                    if (acceptCheck == 1)  //this means we did accept the new neighborhood
                    {
                        s_current = new VRP(s_neighbor);
                        break;   //this takes us out of the if loop for routelist looping and back to the while loop
                    }
                    if (acceptCheck == 0) //this means we did not accept the new neighborhood
                    {
                        counter += 1;   //increment the nubmer of times we rejected
                        //Console.WriteLine("don't accpet");
                        continue;   //this takes us to the top of the list to the next pair on the routelist
                    }


                }  //end for loop for the route pairs

            }   //end time check while


            Feasibility.check(s_best);   //here we make sure all the values stored in the VRP network for our final solution are not null

            watch.Stop();                                       //after the algorithm is complet, stop the clock
            double elapsedMS = watch.ElapsedMilliseconds;       //compute the time in milliseconds
            RouteWrite.Outputroutes(originalnetwork, s_best, elapsedMS, inputfile);       //output the results using the RouteWrite class  
            Console.ReadKey();
        }

        private static CVRPSolution SavingsMethodHeuristic()
        {
            Console.WriteLine("Starting the SavingsMethodHeuristic");

            //The savings list
            List<SavingsCouple> Savings = new List<SavingsCouple>();
            //Go over all possible couples once and create a coupling, we rely on the fact that the distances are symmetric
            for (int i = 1; i < Program.vrpData.Dimension; i++)
            {
                for (int j = 1; j < Program.vrpData.Dimension; j++)
                {
                    if (j != i)
                    {
                        SavingsCouple cpl = new SavingsCouple();
                        cpl.FirstNode = i;
                        cpl.SecondNode = j;
                        cpl.Saving = Program.vrpData.Distances[i, 0] + Program.vrpData.Distances[0, j] - Program.vrpData.Distances[i, j];
                        Savings.Add(cpl);
                    }
                }

            }

            Savings = Savings.OrderByDescending(x => x.Saving).ToList();

            // Current tour list. Populated in the following loop, and will have tours removed and added as the heuristic progresses.
            List<VehicleRoute> Tours = new List<VehicleRoute>();
            // List of nodes that are either at the start of a tour or at the end. These can be merged. Initially all nodes are in the list.
            List<int> availNodes = new List<int>();
            // Create the inital tours
            Console.WriteLine("Start creating the initial routes");
            for (int i = 1; i < Program.vrpData.Dimension; i++)
            {
                VehicleRoute tour = new VehicleRoute(i);
                tour.totalDemandOnRoute = vrpData.Demands[i];
                tour.totalDistanceOfRoute = 2 * vrpData.Distances[0, i];
                Tours.Add(tour);
                availNodes.Add(i);
            }
            Console.WriteLine("Finished creating the initial routes");

            //We will iterate through the savings list
            for (int i = 0; i < Savings.Count; i++)
            {
                //flag variable that indicate if both nodes in savings couple are at the extremites of a tour
                int flag = 0;

                //check if the nodes are in the extremites
                for (int j = 0; j < availNodes.Count; j++)
                    if ((availNodes[j] == Savings[i].FirstNode) || (availNodes[j] == Savings[i].SecondNode))
                        flag++;

                //If the nodes are at the extremities, try to merge
                if (flag == 2)
                {
                    //Console.WriteLine("Trying to merge since nodes are extremeties");
                    //we need to find the two tours that contain the nodes
                    //id of the tours
                    int indexOfFirstRoute = -1;
                    int indexOfSecondRoute = -1;

                    for (int j = 0; j < Tours.Count; j++)
                    {
                        //We found the tour that finishes with the first node
                        if (Tours[j].GetNodeAt(Tours[j].GetNumberOfNodesVisited()) == Savings[i].FirstNode)
                            indexOfFirstRoute = j;
                        //We found the tour that starts with the second node
                        if (Tours[j].GetNodeAt(1) == Savings[i].SecondNode)
                            indexOfSecondRoute = j;
                    }

                    // Merge routes if:
                    // 1. pair from savings finishes one route and starts another
                    // 2. its not the same route
                    // 3. capacity not violated by merging
                    if (indexOfSecondRoute >= 0 && indexOfFirstRoute >= 0 && indexOfSecondRoute != indexOfFirstRoute && Tours[indexOfFirstRoute].totalDemandOnRoute + Tours[indexOfSecondRoute].totalDemandOnRoute <= Program.vrpData.Capacity)
                    {
                        int newlength = Tours[indexOfFirstRoute].GetNumberOfNodesVisited() + Tours[indexOfSecondRoute].GetNumberOfNodesVisited();

                        // Create a new sequence of nodes which corresponds to the merged route. It will include nodes from both routes
                        List<int> tour = new List<int>();
                        double distCalculated = 0;
                        tour.Add(0);
                        int j = 0;
                        for (j = 0; j < newlength; j++)
                        {
                            if (j < Tours[indexOfFirstRoute].GetNumberOfNodesVisited())
                                tour.Add(Tours[indexOfFirstRoute].GetNodeAt(j + 1));
                            else
                            {
                                //subtract the length of tour A
                                int normIndex = j - Tours[indexOfFirstRoute].GetNumberOfNodesVisited();
                                tour.Add(Tours[indexOfSecondRoute].GetNodeAt(normIndex + 1));
                            }
                            distCalculated += vrpData.Distances[tour[j], tour[j + 1]];
                        }
                        distCalculated += vrpData.Distances[tour[j], 0];
                        tour.Add(0);
                        VehicleRoute Tour = new VehicleRoute(tour);
                        Tour.totalDistanceOfRoute = distCalculated;
                        Tour.totalDemandOnRoute = Tours[indexOfFirstRoute].totalDemandOnRoute + Tours[indexOfSecondRoute].totalDemandOnRoute;
                        //add the combined tour and remove the old ones
                        Tours.Add(Tour);

                        // If the any of the tours merged are of length greater than 2, their corresponding extreme (starting or ending) node cannot
                        // be merged anymore. It can be removed from the savings list.
                        if (Tours[indexOfFirstRoute].GetNumberOfNodesVisited() > 1)
                            availNodes.Remove(Tours[indexOfFirstRoute].GetLastNodeVisited());
                        if (Tours[indexOfSecondRoute].GetNumberOfNodesVisited() > 1)
                            availNodes.Remove(Tours[indexOfSecondRoute].GetNodeAt(1));

                        // Remove the merged routes from the route list.
                        Tours.RemoveAt(indexOfFirstRoute);
                        if (indexOfFirstRoute > indexOfSecondRoute)
                            Tours.RemoveAt(indexOfSecondRoute);
                        else
                            Tours.RemoveAt(indexOfSecondRoute - 1);
                    }
                }
            }

            //Tours now contain the solution
            CVRPSolution sol = new CVRPSolution();
            sol.listOfRoutes = new List<VehicleRoute>();

            double heuristicTotalCost = 0;
            for (int i = 0; i < Tours.Count; i++)
            {
                sol.listOfRoutes.Add(Tours[i]);
                heuristicTotalCost += Program.vrpData.Distances[0, sol.listOfRoutes[i].GetNodeAt(1)] + Program.vrpData.Distances[sol.listOfRoutes[i].GetLastNodeVisited(), 0];
                for (int j = 0; j < sol.listOfRoutes[i].GetNumberOfNodesVisited() - 1; j++)
                    heuristicTotalCost += Program.vrpData.Distances[sol.listOfRoutes[i].GetNodeAt(j + 1), sol.listOfRoutes[i].GetNodeAt(j + 2)];
            }
            sol.totalCost = heuristicTotalCost;
            Console.WriteLine("Heuristic done.\nTotalcost : " + sol.totalCost);
            return sol;
        }
    }
}
